package algorithm.graph.adjacencylist;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.function.Consumer;

public class EulerRoute {
    AdjacencyListGraph graph;

    public EulerRoute(AdjacencyListGraph graph) {
        this.graph = graph;
    }

    public void find(int start, Consumer<Edge[]> onVisit) {
        Node[] nodeArray = graph.getNodeArray();
        List<Edge> unvisitedEdgeList = new ArrayList<>();
        Arrays.stream(nodeArray).forEach(it -> {
            it.getEdgeList().forEach(it1 -> {
                if (graph.isDirected()) {
                    unvisitedEdgeList.add(it1);
                } else {
                    if (!isContainsEdge(unvisitedEdgeList, it1)) {
                        unvisitedEdgeList.add(it1);
                    }
                }
            });
        });
        List<Edge> visitedEdgeList = new ArrayList<>();
        List<Edge> path = new ArrayList<>();
        doVisitEdge(start, unvisitedEdgeList, visitedEdgeList, path, onVisit);
    }

    private void doVisitEdge(int start, List<Edge> unVisitedEdgeList, List<Edge> visitedEdge,
                             List<Edge> path, Consumer<Edge[]> onVisit) {
        Node[] nodeArray = graph.getNodeArray();
        List<Edge> edgeList = nodeArray[start].getEdgeList();
        if (edgeList.stream().allMatch(it -> isContainsEdge(visitedEdge, it))) {
            if (path.size() == unVisitedEdgeList.size()) {
                onVisit.accept(path.toArray(new Edge[path.size()]));
            }
        } else {
            edgeList.forEach(it -> {
                if (!isContainsEdge(visitedEdge, it)) {
                    addEdge(visitedEdge, it);
                    path.add(it);
                    doVisitEdge(it.to, unVisitedEdgeList, visitedEdge, path, onVisit);
                    path.remove(it);
                    removeEdge(visitedEdge, it);
                }
            });
        }
    }

    private void addEdge(List<Edge> visitedEdge, Edge edge) {
        visitedEdge.add(edge);
    }

    private void removeEdge(List<Edge> visitedEdge, Edge edge) {
        Iterator<Edge> iterator = visitedEdge.iterator();
        while (iterator.hasNext()) {
            Edge next = iterator.next();
            if (isEdgeEqual(next, edge, graph.isDirected())) {
                iterator.remove();
            }
        }
    }

    private boolean isEdgeEqual(Edge o1, Edge o2, boolean isDirected) {
        if (isDirected) {
            return o1.from == o2.from && o1.to == o2.to;
        } else {
            return Math.min(o1.from, o1.to) == Math.min(o1.from, o1.to)
                    && Math.max(o2.from, o2.to) == Math.max(o2.from, o2.to);
        }
    }

    private boolean isContainsEdge(List<Edge> visitedEdge, Edge edge) {
        return visitedEdge.stream().filter(it -> isEdgeEqual(it, edge, graph.isDirected())).toList().size() == 1;
    }
}
